﻿using System.Text;

Solution solution = new Solution();
// add your code here for debugging

Console.WriteLine("return n switch");
Console.WriteLine("{");
for (int i = 1; i <= 9; i++)
{
    var q = SolveNQueens(i).Count;
    Console.WriteLine($"{i}=>{q},");
}
Console.WriteLine("_=>throw new NotImplementedException()");
Console.WriteLine("};");

#region 来自 NQueens
IEnumerable<Board> PutAQueen(IEnumerable<Board> boards)
{
    foreach (var board in boards)
    {
        foreach (var (x, y) in board.AvailablePositionsAfterLastPlace)
            yield return board.PutQueenOnNewBoard(x, y);
    }
}

IList<IList<string>> SolveNQueens(int n)
{
    IEnumerable<Board> boards = new Board[] { new Board(n) };
    for (int i = 0; i < n; i++)
        boards = PutAQueen(boards);
    var linq = from board in boards
               select (IList<string>)(board.ToStrings().ToList());
    return linq.ToList();
}

class Board
{
    /// <summary>
    /// 用 <c>null</c> 表示这里有皇后，<code>true</code> 表示可以放这里不会被其他皇后吃，<code>false</code> 表示不可以放。
    /// </summary>
    private readonly bool?[,] board;

    private readonly (int x, int y) nextPlace;

    public int Size => this.board.GetLength(0);
    public Board(int size)
        : this(size, (0, 0), true) { }
    private Board(int size, (int x, int y) nextPlace, bool setToTrue)
    {
        this.nextPlace = nextPlace;
        this.board = new bool?[size, size];
        if (setToTrue)
        {
            for (int i = 0; i < size; i++)
            {
                for (int j = 0; j < size; j++)
                    this.board[i, j] = true;
            }
        }
    }

    public Board PutQueenOnNewBoard(int x, int y)
    {
        var size = this.Size;
        var copy = new Board(size, (x, y + 1), false);
        Array.Copy(this.board, copy.board, this.board.Length);

        for (int i = x + 1, j = y + 1; i < size && j < size; i++, j++)
            copy.board[i, j] = false;

        for (int i = x - 1, j = y - 1; i >= 0 && j >= 0; i--, j--)
            copy.board[i, j] = false;

        for (int i = x - 1, j = y + 1; i >= 0 && j < size; i--, j++)
            copy.board[i, j] = false;

        for (int i = x + 1, j = y - 1; i < size && j >= 0; i++, j--)
            copy.board[i, j] = false;

        for (int i = 0; i < size; i++)
            copy.board[i, y] = false;

        for (int j = 0; j < size; j++)
            copy.board[x, j] = false;

        copy.board[x, y] = null;

        return copy;
    }

    public IEnumerable<string> ToStrings()
    {
        for (int i = 0; i < this.board.GetLength(0); i++)
        {
            StringBuilder stringBuilder = new StringBuilder();
            for (int j = 0; j < this.board.GetLength(1); j++)
                _ = stringBuilder.Append(this.board[i, j] == null ? 'Q' : '.');
            yield return stringBuilder.ToString();
        }
    }

    public IEnumerable<(int x, int y)> AvailablePositionsAfterLastPlace
    {
        get
        {
            for (int j = this.nextPlace.y; j < this.board.GetLength(1); j++)
            {
                if (this.board[this.nextPlace.x, j] == true)
                    yield return (this.nextPlace.x, j);
            }

            for (int i = this.nextPlace.x + 1; i < this.board.GetLength(0); i++)
            {
                for (int j = 0; j < this.board.GetLength(1); j++)
                {
                    if (this.board[i, j] == true)
                        yield return (i, j);
                }
            }
        }
    }
}
#endregion